<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1">
        <title>10-数据结构与算法设计 - Adbean&#39;s Blog</title><meta name="Description" content="Adbean&#39;s Blog"><meta property="og:title" content="10-数据结构与算法设计" />
<meta property="og:description" content="Bubble Sort 冒泡排序 Bubble Sort the list: 33, 56, 17, 8, 95, 22 Make sure the final result is from small to large. Write out the list after the 2nd pass. 冒泡排序原理（升序） 比较相邻的元素。如果前一个元素比后一个元素大，就交换" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://adbean.gitee.io/posts/my-tenth-post/" />
<meta property="og:image" content="https://adbean.gitee.io/logo.png"/>
<meta property="article:published_time" content="2020-11-08T23:14:22+08:00" />
<meta property="article:modified_time" content="2020-11-08T23:14:22+08:00" />
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://adbean.gitee.io/logo.png"/>

<meta name="twitter:title" content="10-数据结构与算法设计"/>
<meta name="twitter:description" content="Bubble Sort 冒泡排序 Bubble Sort the list: 33, 56, 17, 8, 95, 22 Make sure the final result is from small to large. Write out the list after the 2nd pass. 冒泡排序原理（升序） 比较相邻的元素。如果前一个元素比后一个元素大，就交换"/>
<meta name="application-name" content="Adbean&#39;s Blog">
<meta name="apple-mobile-web-app-title" content="Adbean&#39;s Blog"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="icon" href="../../Owl.ico"><link rel="apple-touch-icon" sizes="180x180" href="../../apple-touch-icon.png"><link rel="mask-icon" href="../../safari-pinned-tab.svg" color="#5bbad5"><link rel="manifest" href="../../site.webmanifest"><link rel="canonical" href="https://adbean.gitee.io/posts/my-tenth-post/" /><link rel="prev" href="https://adbean.gitee.io/posts/my-ninth-post/" /><link rel="next" href="https://adbean.gitee.io/posts/my-sixth-project/" /><link rel="stylesheet" href="../../lib/normalize/normalize.min.css"><link rel="stylesheet" href="../../css/style.min.css"><link rel="stylesheet" href="../../lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="../../lib/animate/animate.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "10-数据结构与算法设计",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/adbean.gitee.io\/posts\/my-tenth-post\/"
        },"genre": "posts","keywords": "作业, 算法","wordcount":  699 ,
        "url": "https:\/\/adbean.gitee.io\/posts\/my-tenth-post\/","datePublished": "2020-11-08T23:14:22+08:00","dateModified": "2020-11-08T23:14:22+08:00","publisher": {
            "@type": "Organization",
            "name": "Adbean"},"author": {
                "@type": "Person",
                "name": "Adbean"
            },"description": ""
    }
    </script></head>
    <body header-desktop="fixed" header-mobile="auto"><script type="text/javascript">(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('dark' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'dark' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="../../" title="Adbean&#39;s Blog"><img
        class="lazyload logo"
        src="../../svg/loading.min.svg"
        data-src="../../Owl.ico"
        data-srcset="../../Owl.ico, ../../Owl.ico 1.5x, ../../Owl.ico 2x"
        data-sizes="auto"
        alt="/Owl.ico"
        title="/Owl.ico" />Adbean&#39;s Blog</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="../../"> 主页 </a><a class="menu-item" href="../../posts/"> 文章 </a><a class="menu-item" href="../../posts/my-index/"> 索引 </a><a class="menu-item" href="../../tags/"> 标签 </a><a class="menu-item" href="../../categories/"> 分类 </a><span class="menu-item delimiter"></span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="../../" title="Adbean&#39;s Blog"><img
        class="lazyload logo"
        src="../../svg/loading.min.svg"
        data-src="../../Owl.ico"
        data-srcset="../../Owl.ico, ../../Owl.ico 1.5x, ../../Owl.ico 2x"
        data-sizes="auto"
        alt="/Owl.ico"
        title="/Owl.ico" />Adbean&#39;s Blog</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><a class="menu-item" href="../../" title="">主页</a><a class="menu-item" href="../../posts/" title="">文章</a><a class="menu-item" href="../../posts/my-index/" title="">索引</a><a class="menu-item" href="../../tags/" title="">标签</a><a class="menu-item" href="../../categories/" title="">分类</a><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                <i class="fas fa-adjust fa-fw"></i>
            </a></div>
    </div>
</header>
<div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div>
<main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single"><h1 class="single-title animated flipInX">10-数据结构与算法设计</h1><div class="post-meta">
            <div class="post-meta-line"><span class="post-author"><a href="https://adbean.gitee.io/" title="Author" target="_blank" rel="noopener noreffer author" class="author"><i class="fas fa-user-circle fa-fw"></i>Adbean</a></span>&nbsp;<span class="post-category">收录于 <a href="../../categories/%E4%BD%9C%E4%B8%9A/"><i class="far fa-folder fa-fw"></i>作业</a></span></div>
            <div class="post-meta-line"><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2020-11-08">2020-11-08</time>&nbsp;<i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 699 字&nbsp;
                <i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 2 分钟&nbsp;</div>
        </div><div class="details toc" id="toc-static"  kept="">
                <div class="details-summary toc-title">
                    <span>目录</span>
                    <span><i class="details-icon fas fa-angle-right"></i></span>
                </div>
                <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#bubble-sort-冒泡排序">Bubble Sort 冒泡排序</a>
      <ul>
        <li><a href="#冒泡排序原理升序">冒泡排序原理（升序）</a></li>
        <li><a href="#冒泡排序伪代码">冒泡排序伪代码</a></li>
        <li><a href="#冒泡排序动画">冒泡排序动画</a></li>
      </ul>
    </li>
    <li><a href="#insertion-数组插入">Insertion 数组插入</a>
      <ul>
        <li><a href="#算法设计">算法设计</a></li>
      </ul>
    </li>
    <li><a href="#stack-栈">Stack 栈</a></li>
  </ul>
</nav></div>
            </div><div class="content" id="content"><h2 id="bubble-sort-冒泡排序">Bubble Sort 冒泡排序</h2>
<p><strong>Bubble Sort the list</strong>: 33, 56, 17, 8, 95, 22</p>
<p>Make sure the final result is <strong>from small to large</strong>.</p>
<p>Write out the list <strong>after the 2nd pass.</strong></p>
<h3 id="冒泡排序原理升序">冒泡排序原理（升序）</h3>
<ol>
<li>比较<strong>相邻的元素</strong>。如果前一个元素比后一个元素大，就交换这两个元素的位置。</li>
<li>对<strong>每一对相邻元素</strong>做同样的工作，从开始第一对元素到结尾的后一对元素。<strong>终后位置</strong>的元素就是最大值。</li>
</ol>
<h3 id="冒泡排序伪代码">冒泡排序伪代码</h3>
<pre><code class="language-Pseudocode" data-lang="Pseudocode">READ NUMS
LEN &lt;- length of NUMS
FOR (i FROM 0 to LEN - 1)
    FOR (j FROM 0 TO LEN - 1 - i)
        IF (array[j] &gt; array[j + 1]) THEN
            SWAP(NUMS[j], NUMS[j + 1])
        END
    END
END
</code></pre><h3 id="冒泡排序动画">冒泡排序动画</h3>
<p><img
        class="lazyload"
        src="../../svg/loading.min.svg"
        data-src="../../bubblesort.gif"
        data-srcset="../../bubblesort.gif, ../../bubblesort.gif 1.5x, ../../bubblesort.gif 2x"
        data-sizes="auto"
        alt="/bubblesort.gif"
        title="bubblesort" /></p>
<p>上图展示了冒泡排序的第一轮和第二轮，其中<strong>最右边深紫色的为数组中最大的元素</strong>。</p>
<p>所以当第二轮结束后，排序后的数组为 17，8，33，22，56，95</p>
<p><img
        class="lazyload"
        src="../../svg/loading.min.svg"
        data-src="../../bubblesort_all.gif"
        data-srcset="../../bubblesort_all.gif, ../../bubblesort_all.gif 1.5x, ../../bubblesort_all.gif 2x"
        data-sizes="auto"
        alt="/bubblesort_all.gif"
        title="bubblesort" /></p>
<p>上图为<strong>冒泡排序的全过程</strong></p>
<h2 id="insertion-数组插入">Insertion 数组插入</h2>
<p>Give a <strong>sorted array</strong> as list={ 60, 65, 75, 80, 90, 95 }.</p>
<p>Design an algorithm to <strong>insert</strong> the value of x into the <strong>sorted array</strong>. Then test the algorithm with value <strong>50</strong>,<strong>67</strong>,<strong>99</strong>.</p>
<p>思考：为什么选择插入点在 list <strong>头</strong>上、<strong>中间</strong>、<strong>尾巴</strong>上的三个数作为算法测试的数据，你能解释吗？</p>
<h3 id="算法设计">算法设计</h3>
<pre><code class="language-Pseudocode" data-lang="Pseudocode">READ NUMS, TARGET
LEN &lt;- length of NUMS
LEFT &lt;- 0
RIGHT &lt;- LEN - 1
WHILE (LEFT &lt;= RIGHT)
{
    MID &lt;- (LEFT + RIGHT) / 2
    IF (NUMS[MID] &gt; TARGET)
    {
        RIGHT &lt;- (MID - 1)
    }
    ELSE IF (NUMS[MID] &lt; TARGET)
    {
        LEFT &lt;- (MID + 1)
    }
    ELSE IF (NUMS[MID] == TARGET)
    {
        BREAK;
    }
}
IF (NUMS[LEFT] &lt; TARGET)
{
    BACK &lt;- LEN
    WHILE(BACK &gt; LEFT)
    {
        NUMS[BACK] = NUMS[BACK - 1]
        BACK &lt;- (BACK - 1)
    }
    NUMS[LEFT + 1] = TARGET
}
ELSE IF (NUMS[LFET] &gt; TARGET)
{
    BACK &lt;- LEN
    WHILE(BACK &gt;= LEFT)
    {
        NUMS[BACK] = NUMS[BACK - 1]
        BACK &lt;- (BACK - 1)
    }
    NUMS[LEFT] = TARGET
}
</code></pre><p>因为是<strong>有序（升序）的排序数组</strong>插入，所以可以使用<strong>二分查找</strong>搜索到插入的位置，然后<strong>移动数组插入</strong>该数字</p>
<p>但是由于是<strong>有序数组</strong>，实际上在插入之前，我们可以使用排序数组的头和尾部与插入目标数进行比较，若目标数小于数组头，则直接插在数组的头部；若目标数大于数组尾，则直接插在数组的尾部；若目标数大于数组头且小于数组尾，则使用二分查找找到位置后插入。</p>
<h2 id="stack-栈">Stack 栈</h2>
<p>What is the state of the <strong>stack</strong> after the following sequence of <strong>Push</strong> and <strong>Pop</strong> operations?</p>
<ol>
<li>Push “anne”</li>
<li>Push “get”</li>
<li>Push “your”</li>
<li>Pop</li>
<li>Push “my”</li>
<li>Push “gun”</li>
</ol>
<p><img
        class="lazyload"
        src="../../svg/loading.min.svg"
        data-src="../../stack.gif"
        data-srcset="../../stack.gif, ../../stack.gif 1.5x, ../../stack.gif 2x"
        data-sizes="auto"
        alt="/stack.gif"
        title="stack" /></p>
<p>所以这个栈的<strong>最终状态</strong>是（从栈底往栈顶读）: anne get my gun</p>
</div><div class="post-footer" id="post-footer">
    <div class="post-info">
        <div class="post-info-line">
            <div class="post-info-mod">
                <span>更新于 2020-11-08</span>
            </div>
            <div class="post-info-license"></div>
        </div>
        <div class="post-info-line">
            <div class="post-info-md"></div>
            <div class="post-info-share">
                <span></span>
            </div>
        </div>
    </div>

    <div class="post-info-more">
        <section class="post-tags"><i class="fas fa-tags fa-fw"></i>&nbsp;<a href="../../tags/%E4%BD%9C%E4%B8%9A/">作业</a>,&nbsp;<a href="../../tags/%E7%AE%97%E6%B3%95/">算法</a></section>
        <section>
            <span><a href="javascript:void(0);" onclick="window.history.back();">返回</a></span>&nbsp;|&nbsp;<span><a href="../../">主页</a></span>
        </section>
    </div>

    <div class="post-nav"><a href="../../posts/my-ninth-post/" class="prev" rel="prev" title="09-面向对象编程语言"><i class="fas fa-angle-left fa-fw"></i>09-面向对象编程语言</a>
            <a href="../../posts/my-sixth-project/" class="next" rel="next" title="Python 交互式编程">Python 交互式编程<i class="fas fa-angle-right fa-fw"></i></a></div>
</div>
</article></div>
            </main><footer class="footer">
        <div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.74.3">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/dillonzq/LoveIt" target="_blank" rel="noopener noreffer" title="LoveIt 0.2.10"><i class="far fa-kiss-wink-heart fa-fw"></i> LoveIt</a>
                </div><div class="footer-line"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2020 - 2021</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="https://adbean.gitee.io/" target="_blank">Adbean</a></span>&nbsp;|&nbsp;<span class="license"><a rel="license external nofollow noopener noreffer" href="https://creativecommons.org/licenses/by-nc/4.0/" target="_blank">CC BY-NC 4.0</a></span></div>
        </div>
    </footer></div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-arrow-up fa-fw"></i>
            </a><a href="#" id="view-comments" class="fixed-button" title="查看评论">
                <i class="fas fa-comment fa-fw"></i>
            </a>
        </div><link rel="stylesheet" href="../../lib/katex/katex.min.css"><link rel="stylesheet" href="../../lib/katex/copy-tex.min.css"><script type="text/javascript" src="../../lib/smooth-scroll/smooth-scroll.min.js"></script><script type="text/javascript" src="../../lib/lazysizes/lazysizes.min.js"></script><script type="text/javascript" src="../../lib/clipboard/clipboard.min.js"></script><script type="text/javascript" src="../../lib/katex/katex.min.js"></script><script type="text/javascript" src="../../lib/katex/auto-render.min.js"></script><script type="text/javascript" src="../../lib/katex/copy-tex.min.js"></script><script type="text/javascript" src="../../lib/katex/mhchem.min.js"></script><script type="text/javascript">window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":50},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false}};</script><script type="text/javascript" src="../../js/theme.min.js"></script></body>
</html>
